1. Field of the Invention
The present invention is utilized for asynchronous transfer mode (ATM) communications and is suitable for use in ATM communication networks in which there are cells of different service classes. This invention was developed for application to cells in ATM communications, but it is also widely applicable to packet based communications other than ATM.
2. Description of the Related Art
In ATM communications, information is transmitted and received after being placed in fixed-length packets called cells. If there are a large number of cells for the same destination and these cells are output simultaneously to the same line, collisions will occur between cells. As a result, there will be an increase in the number of dropped cells. If the number of dropped cells increases, retransmission at the source becomes necessary, with the result that the efficiency of information transfer of the ATM network decreases.
In order to avoid such a situation, control aimed at preventing cell collisions is performed at ATM switches and other devices that control the direction of cell output. This is called contention control. Conventional contention control circuits will be explained with reference to FIGS. 21-22. FIG. 21 shows the overall configuration of a conventional contention control circuit, while FIG. 22 shows the overall configuration of a conventional contention control circuit in an ATM network includes cells of different service classes.
In FIG. 21, the conventional contention control circuit includes input lines 1-1 to 1-4, read control circuits 17-1 to 17-4, a ring arbiter 65, and queuing buffers 4-1 to 4-4. Cells A to D which have been transferred from input lines 1-1 to 1-4 are temporarily stored in queuing buffers 4-1 to 4-4. When cells arrive or are queuing, read control circuits 17-1 to 17-4 send a read request to ring arbiter 65. Ring arbiter 65 sends a read permission in response to any read control circuit 17-1 to 17-4 which has issued a read request.
Next, an explanation will be given of a conventional contention control circuit in an ATM network which includes cells of different service classes. As shown in FIG. 22, buffer units 2-1 to 2-4 respectively comprise high priority class (hereinafter termed H class) buffers 4-1 to 4-4 and low priority class (hereinafter termed L class) buffers 5-1 to 5-4. Input line 1-1 (#1) will be taken as an example and an explanation given of the operation of buffer unit 2-1.
When a cell is input to buffer unit 2-1, a control unit (not illustrated) of buffer unit 2-1 refers to the quality class identifier in the cell header and thereby recognizes whether the cell is an H class cell or an L class cell. The cell is then allocated by selector 33-1 to either H class buffer 4-1 or L class buffer 5-1.
In buffer unit 2-1, cells AH1, AH2 and AH3 are stored in H class buffer 4-1, and cell AL1 is stored in L class buffer 5-1. When an H class cell is stored, selector 6-1 preferentially selects the H class cell regardless of whether an L class cell is present. An L class cell is selected by selector 6-1 only when no H class cell is stored in H class buffer 4-1.
Buffer units 2-1 to 2-4 therefore send cell output request signals to contention control unit 90 for the following cells, respectively: H class cell AH1, L class cell BL1, L class cell CL1, and L class cell DL1.
Assuming that the send permission in ring arbiter 65 is presently at input line 1-1 (#1), cell AH1 is sent first. Next, the send permission is given to input line 1-2 (#2) and cell BL1 is sent. In the same way, cells CL1, DL1, AH2 and BL2 are subsequently sent.
The ring arbiter of a conventional contention control circuit of this sort guarantees only the equality of the number of reads of each input line 1-1 to 1-4. It does not guarantee that the order in which cells arrive is maintained.
For example, FIG. 23 is a timing chart showing an output of the conventional contention control circuit illustrated in FIG. 21. Although cell C on input line 1-3 (#3) has arrived later than the other cells A, B and D, as shown in FIG. 23, cell C (arrived at t=3) is read before cell D (arrived at t=1). Thus, the overall temporal order is not guaranteed, and only the equality of the number of reads of each input line is guaranteed. In this example, it is assumed that there were no cells queuing in buffers 4-1 to 4-4 apart from cells A, B, C and D.
In the case of a conventional contention control circuit in an ATM network including cells of different service classes (such as shown in FIG. 22), if many H class cells are stored in the buffer unit for a particular input line, L class cells from other input lines are read first in order to maintain the equality of the number of reads of each input line.
FIG. 24 is a timing chart showing the output of the conventional contention control circuit illustrated in FIG. 22. In this example, after H class cell AH1 has been output from buffer unit 2-1, L class cell BL1 is output from buffer unit 2-2, and then L class cell CL1 is output from buffer unit 2-3 and L class cell DL1 is output from buffer unit 2-4, despite H class cells AH2 and AH3 still remaining in buffer unit 2-1. Thus, H class cell AH2 is finally output after L class cell DL1 has been output from buffer unit 2-4. Consequently, the quality of the H class can deteriorate.
A further problem is that in the case of a large-scale ATM switch, because the ring arbiter has to monitor all the read control circuits, it takes a considerable time for the ring arbiter to make one round of all the circuits. Another problem is that to extend the switch, after the number of input lines has been increased, it is necessary to perform troublesome operations such as modifying the programs of the ring arbiter, which has overall control of the contention control circuit. This results in poor extendibility.